use std::rc::Rc;
use std::cell::RefCell;
use std::cmp::Ordering;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

struct Pair(i32, Option<Rc<RefCell<TreeNode>>>);

struct Solution;

impl Solution {
    /// 个人解法
    pub fn subtree_with_all_deepest_self_solution(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        let depth = Solution::depth(root.clone());
        Solution::smallest_subtree_with_all_the_deepest_nodes_self_help(depth, root)
    }

    // 计算深度
    fn depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        if let Some(root_rc) = root {
            let left = Solution::depth(root_rc.borrow().left.clone());
            let right = Solution::depth(root_rc.borrow().right.clone());
            return i32::max(left, right) + 1;
        }
        0
    }

    /// 辅助函数
    /// 思路如下
    /// 根节点特定是所有最深节点的祖节点。现在是检索它的左子树和右子树是最深
    /// 节点的祖节点。如果都是，那么应该返回根节点。如果一个是一个不是，继续
    /// 递归是的子节点
    /// 递归的终止条件就是最底层那个节点，它铁定是自身的祖节点的。直接返回
    fn smallest_subtree_with_all_the_deepest_nodes_self_help(depth: i32, root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        if let Some(root_rc) = root.clone() {
            if depth == 1 {
                return root;
            }
            let left = Solution::smallest_subtree_with_all_the_deepest_nodes_self_help(depth - 1, root_rc.borrow().left.clone());
            let right = Solution::smallest_subtree_with_all_the_deepest_nodes_self_help(depth - 1, root_rc.borrow().right.clone());

            return match (left.is_some(), right.is_some()) {
                (true, true) => root,
                (true, false) => left,
                (false, true) => right,
                (false, false) => None,
            };
        }
        None
    }


    /// 社区解法
    /// 思路差不多，但是把深度判断和节点判断结合了
    fn subtree_with_all_deepest(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        Solution::smallest_subtree_with_all_the_deepest_nodes_help(root).1
    }

    fn smallest_subtree_with_all_the_deepest_nodes_help(root: Option<Rc<RefCell<TreeNode>>>) -> Pair {
        if let Some(root_rc) = root.clone() {
            let left_pair = Solution::smallest_subtree_with_all_the_deepest_nodes_help(root_rc.borrow().left.clone());
            let right_pair = Solution::smallest_subtree_with_all_the_deepest_nodes_help(root_rc.borrow().right.clone());


            return Pair(
                i32::max(left_pair.0, right_pair.0) + 1,
                match left_pair.0.cmp(&right_pair.0) {
                    Ordering::Less => right_pair.1,
                    Ordering::Equal => root,
                    Ordering::Greater => left_pair.1
                },
            );
        }
        Pair(0, None)
    }
}

fn main() {
    Solution::subtree_with_all_deepest_self_solution(None);
    Solution::subtree_with_all_deepest(None);
}

